Computer processors function by processing data elements through various registers in accordance with instructions provided by a computer program. The processor executes instructions in the form of machine language, which are the low-level instructions relating to what data elements are processed through which registers. Most software, however, is written in higher-level programming code, such as C++, which has the advantages of being human readable and of embodying relatively complex processing operations using comparatively short, quickly-written commands. A compiler receives the high-level programming code, and based upon the programming of the compiler itself, generates the machine language that is readable by a processor.
Single Instruction Multiple Data (SIMD) operations are a known way of enhancing the performance (i.e., speed) of processors. Generally speaking, SIMD operations enhance performance by efficiently handling large quantities of data in parallel. Processors with SIMD capability are currently used in a wide range of machines, e.g., supercomputers, personal computers, game machines, etc. In order to realize the advantages of SIMD, these processors must be provided with machine language code having SIMD instructions. Accordingly, compilers have been developed that generate SIMD code from programs written in standard high-level languages.
The automatic generation of SIMD code, via a compiler with SIMD capability, is generally well understood for code that is parallel. Although the presence of non-aligned (e.g., not parallel) data elements adds considerable complexity to the generation of SIMD code, methods have been developed for handling such instances. For example, a compiler may track the alignment of each of the data involved in the computation and shift the alignment of the data in registers so as to generate valid SIMD code. However, the shifting may result in the generation of invalid code in the presence of dependences.
Data dependences are statements within the source code that depend on each other. For example, the definition of a new value in a first statement and the subsequent use of the defined value in a second statement creates a dependence between the statements. Dependences often exist in iterative loops where statements are commonly re-defined and re-used in each iteration. Dependences between statements enforce an ordering between the statements that, if violated, would result in an invalid code that generates erroneous results.
Dependences interact with automatic SIMD code generation (also referred to as “simdization”) because the statements in a loop to be simdized must be re-ordered in order to satisfy the above-mentioned alignment constraints. Dependences between statements constrain the type of re-ordering that is legal, and, therefore, constrain simdization.
Because of these problems, compilers have been quite conservative when simdizing code in the presence of dependences. One rule typically followed is that when the dependence distance is large enough, then the compiler can simdize regardless of the alignment. More advanced compilers may use compile-time alignment information, when available, to further refine the minimum dependence distance required to simdize the code without violating the dependence.
These approaches, however, are unsatisfactory because empirical evidence in real world application indicates that a large fraction of dependences are very short. Compilers of the current technology simply do not simdize loops with such short dependences, and, in many instances, fail to provide the enhanced performance that SIMD is capable of achieving.